package com.LeetCode.Array;

import org.junit.Test;

/**
 * 分割数组，使得左边的数字都小于右边的数字
 */
public class cutArray {

    public int partitionDisjoint(int[] A) {
        int len = A.length;
        int[] maxLeft = new int[len];
        int[] minRight = new int[len];

        int max = A[0];

        for(int i = 0; i < len; i++){
            max = Math.max(max,A[i]);
            maxLeft[i] = max;
        }

        int min = A[len-1];

        for(int i = len - 1; i >= 0; i--){
            min = Math.min(min,A[i]);
            minRight[i] = min;
        }

        for(int i = 1; i < len; i++){
            if(maxLeft[i-1] <= minRight[i] )
                return i;
        }
        return -1;
    }

    @Test
    public void test(){
        int[] arr = {1,1,1,0,6,12};
        System.out.println(partitionDisjoint(arr));
    }
}
